1. Field of the Invention
The present invention relates to a data search method and an apparatus thereof, and more particularly, to a data search method and an apparatus capable of rearranging data addresses in memory space.
2. Description of the Prior Art
Hardware/Software Co-Design is very import for designing system on chip. In Hardware/Software Co-Design, applications required can be formulated previously, such as classifying applications implemented by software or by hardware. The major consideration for those formulations is usually cost and efficiency. Search is a usual demand for network and related application. A specific memory structure is usually utilized on hardware, such as Content Addressable Memory (CAM) with complexity of search time O (1). However, CAM requires expensive hardware and high power consumption, and thus cannot be accepted. On the other hand, conventional Linear Search with higher complexity of search time O (N) is less expensive, where N is data number needs to be searched.
In Binary Search, a memory space is divided into two parts by the values of all data in the memory space, where the data with smaller value are in the first part and the data with larger value arc in the second part. The value of a middle data in the middle of the memory space is compared with the value of a target data. If the value of the target data is smaller than the value of the middle data, the target data is in the first part of the memory space. If the value of the target data is larger than the value of the middle data, the target data is in the second part of the memory space. And if the value of the target data equals the value of the middle data, the target data equals the middle data. For a memory space, having 64 data, it takes at most 6 (log264=6) rounds to find the target data by recursive search.